// 2025/3/2
// https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked
// 两数之和

class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            unordered_multimap<int, int> hash;
            int n = nums.size();
            for(int i = 0; i < n; i++)
            {
                hash.emplace(nums[i], i);
            }
            for(int i = 0; i < n; i++)
            {
                int to_find = target - nums[i];
                auto pr = hash.equal_range(to_find);
                while(pr.first != pr.second)
                {
                    if(pr.first->second == i)
                        ++pr.first;
                    else
                        return {pr.first->second, i};
                }
            }
            return {};
        }
    };